package interview.listflattening;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ListFlattening {
	public int[] breadthFirstFlatten(Node head, int n) {
		int[] result = new int[n];
		int idx = 0;
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(head);
		while(!queue.isEmpty()) {
			Node h = queue.remove();
			while(h != null) {
				result[idx]= h.getData();
				idx++;
				//System.out.println(h.getData());
				if(h.getChild() != null) {
					queue.add(h.getChild());
				}
				h = h.getNext();
			}
		}
		
		return result;
	}
	
	public ArrayList<Integer> breadthFirstFlattenRecursive(Node head) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		Node h = head;
		while(h != null) {
			result.add(h.getData());
			if(h.getChild() != null) {
				result.addAll(breadthFirstFlattenRecursive(h.getChild()));
			}
			h = h.getNext();
		}
		
		return result;
	}
	
	public ArrayList<Integer> depthFirstFlatten(Node head) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		Stack<Node> stack = new Stack<Node>();
		stack.push(head);
		Node current = null;
		
		while(!stack.empty()) {
			current = stack.pop();
			result.add(current.getData());
			if(current.getNext() != null) {
				stack.push(current.getNext());
			}
			if(current.getChild() != null) {				
				stack.push(current.getChild());
			}
		}
		
		return result;
	}
}
